Computer networks have typically been viewed as being divisible into several layers. The Open Systems Interconnection (OSI) reference model established by the International Standards Organization (ISO) defines a computer network as having seven layers. FIG. 1 depicts the seven layers that are defined by the OSI reference model. Layer one is the physical layer, which is responsible for transmitting unstructured bits of information across a link. Layer two is the data link layer. The data link layer is responsible for transmitting chunks of information across a link. Layer three is the network layer. The network layer is responsible for enabling any pair of systems in the computer network to communicate with each other. Layer four is the transport layer. The transport layer is responsible for establishing a reliable communication stream between a pair of systems. Layer five is the session layer, which is responsible for offering services such as dialogue control and chaining. Layer six is the presentation layer, which provides a means by which applications can agree on representations for data. Layer seven is the application layer in which applications such as file transfer services and management services operate.
The Internet protocol (IP) is a layer three network protocol. The IP protocol is a messenger protocol that is part of the Transmission Control Protocol (TCP)/IP protocol suite. TCP is transport layer protocol that facilitate reliable byte stream communication. IP sets forth an addressing scheme that is useful in tracking Internet addresses for different nodes, recognizing incoming messages and forwarding outgoing messages. Each IP packet is a data packet that contains header information and a payload.
IP addresses are 32 bit globally unique addresses that are generally represented in a dotted decimal notation where the dots (i.e. periods) separate the four bytes of the address. An example of an IP address in dotted decimal notation is “1.2.3.4.” Although an IP address is a single 32 bit value, each IP address contains two pieces of information. As shown in FIG. 2, each IP address 10 contains a network identifier 12 and a host identifier 14. The host identifier identifies the host system to which the IP address is assigned. The network identifier identifies the network in which the host system resides.
In order to appreciate how IP addresses are used, it is helpful to consider an example. FIG. 3 shows an example of a computer network in which IP packets are sent between host 20 and host 24. In this example, host 20 is part of network 1 and host 24 is part of network 2. A number of switching nodes 22 interconnect network 1 with network 2. These switching nodes may be switches and/or routers that forward IP packets between network 1 and network 2. Host 24 is host number 97 within network 2. Thus, expressing the address of host 24 in <network, host> form, the IP address for host 24 is <2, 97>. IP packets are forwarded from their source to their destination on a hop by hop basis. Each switching node 22 that an IP packet encounters on the path from host 20 to host 24 constitutes a separate hop. The IP packet has a header that contains a destination IP address. The destination IP address specifies host 24 as the destination. Each switching node 22 on the path between host 20 and host 24 uses the destination address in determining a next hop.
IP addresses were previously divided into three classes: Class A, Class B and Class C. The number of bits allocated to the network identifier 12 in the IP address and the number of bits allocated to the host identifier in the IP address was originally determined by the class of the IP address. With class A IP addresses, the host identifier was allocated three bytes; with class B IP addresses, the host identifier was allocated two bytes; and with class C IP addresses the host identifier was allocated a single byte. Many parties objected to this rigid bit allocation between host identifier and network identifier. As a result, a more flexible scheme was developed where masks were used to identify which bits in an IP address were allocated to the host identifier and which bits were allocated to the network identifier. A number of popular IP routing protocols utilize such masks.
Routers generally include routing tables to assist in forwarding IP packets to their proper destinations. The entries in the routing table hold forwarding information for IP address prefixes (i.e. portions of the IP addresses containing the most significant bits) for which routing information is known. For example, it may be known that all IP packets destined to network 1.2 should be forwarded out over interface A of the node; thus, the entry encodes this knowledge.
FIG. 4A shows an example of four routing table entries 30, 32, 34 and 36. Each routing table entry holds an address 40, a prefix length 42 and an interface 44. The address 40 field contains a prefix of an IP address. The prefix length 42 identifies the length of the prefix within the address field 40. For entry 30, the prefix is only a single byte (i.e. 8 bits) long. The interface 44 identifies the interface to which packets starting with the given prefix may be routed. The interface is a logical abstraction of a port (or other information) that identifies where a range of IP addresses (i.e. the addresses in the range defined by the prefix) should be directed.
FIG. 4B shows an example of the topology of a portion of a computer network wherein the forwarding table entries 30, 32, 34 and 36 are utilized. In particular, node 50 has three interfaces: A, B and C. Interface C leads to network 1. The notation ⅛ in FIG. 4B indicates that the IP address for the network has a prefix value of 1 and that it is 8 bits in length. Interface B leads to a portion of the computer network having IP addresses that start with the prefixes 1.2.3. Interface A leads to destinations having IP addresses that start with the prefix 1.2.4 and 1.2. Specifically, interface A leads to node 52, which, in turn, leads to the other destinations 1.2.4 and 1.2.
For each IP packet received by a node, the longest matching prefix found in the routing table is used to route the IP packet. Consider an IP packet that has a destination address of 1.2.4.7. In such an instance, entries 30, 34 and 36 contain matching prefixes for this IP address. Prefix 1.2.4, however, is the longest prefix and, thus, entry 34 is used to route the IP packet out interface A toward destination 1.2.4.
In conventional routers, the routing table is typically represented as a patricia tree. A patricia tree is a tree data structure that is used to simplify searching of the routing table. The patricia tree employs a binary representation of keys without storing keys in the nodes. FIG. 5 shows an example of a portion of a patricia tree 60. Each node is associated with a particular portion of an IP address prefix. For example, the node b0 is associated with bit 0 of an IP address prefix (i.e. the first bit in an IP address prefix). Each node may contain pointers to child nodes or to terminations. Furthermore each node may have a reference to a routing table entry for the prefix that the node represents. Each pointer leading from a node is associated with a bit value for the next bit in the prefix for the node. The structure is organized as a tree such that each level of the tree represents a successive bit sequence. Thus, node b1 of FIG. 5 represents a two bit sequence in the prefix where the first bit has a value of 0. The table entries are associated with the last node of the prefix. In the example of FIG. 5, entry 62 for the prefix 1, which is one byte in length (or 8 bits in length), is referenced by the node b8 for the prefix bit sequence of “00000001.” Similarly, entry 64 is referenced by the node b16. Terminations, such as termination 65, are provided in the patricia tree to represent prefixes for which there is no associated forwarding table entry.
The patricia tree may also be implemented in a different fashion. The patricia tree may store the table entries so that the pointers point to the table entries (i.e. the table entries are in the tree as nodes). Hence, for a given node, a pointer associated.
The patricia tree provides a convenient search mechanism for conducting a binary search to identify whether any entries are associated with a particular prefix or portion of a prefix. One difficulty with the use of a patricia tree, however, concerns the number of memory accesses that must be performed to utilize the patricia tree. Addressing a node in the patricia tree requires a memory access. Thus, to search down to level 8 of the tree requires 8 memory accesses. Such memory accesses can be quite expensive in terms of time and computational overhead. Given that routers often handle extremely large volumes of IP packets, time and computational overhead are scarce resources that need to be conserved.